Surface reconstruction from imaging data acquired in serial sections or slices of a three-dimensional object constitutes a prerequisite to many medical image processing tasks and applications. A three-dimensional object may be represented by a decision rule and a plurality of volume elements (voxels) piled up in slices comprising rows and columns. Each voxel carries at least one value, preferably an intensity level. The decision rule determines the membership of each voxel to an object in accordance with the at least one value of the voxel. A decision rule for determining the membership of a voxel in a plurality of voxels to a three-dimensional object may comprise a threshold at or above which a voxel is considered to be a member of the object.
Three-dimensional objects comprising a decision rule and a plurality of voxels may be acquired from computed tomography (CT), single photon emission computed tomography (SPECT) or positron emission tomography (PET) scans, or from magnetic resonance imaging (MRI).
Once the membership of each voxel to an object is determined, a surface of the object representation may be obtained by interpolating the slice data. Surface interpolation techniques can be broadly divided into gray-level based interpolation techniques and shape based interpolation techniques.
Gray-level based interpolation, in general, first determines intensity values in intermediate voxel positions by interpolating between adjacent or near voxels to obtain an interpolated intensity value or gray-value. Then, a decision rule is applied to determine object membership of the respective intermediate voxel positions.
In U.S. Pat. No. 6,496,608, Chui describes an image data interpolation method for filling in undefined values in intermediate positions of two-dimensional imaging data.
Gray level based interpolation techniques tend to produce aliasing effects resulting in jagged surface representations. Gray level based interpolation techniques therefore do not appear to be appropriate in applications requiring smooth surface representations, such as surface matching, for instance.
Shape based interpolation in general first extracts object information from slice data by applying a decision rule and obtaining an object representation as binary or discrete volume element or voxel data, for instance. Subsequently the object information is used to guide an interpolation process.
An example of shape-based interpolation is distance field interpolation. The slice data is converted to binary image data using a threshold. Then, a distance transformation is applied to these image data. Distance transformations are described, for example, in Danielsson P.-E., Euclidean Distance Mapping, Computer Graphics and Image Processing, 14, 227-248 (1980). The distance transformation results in a dataset wherein each picture element or pixel contains the distance of that pixel to the surface within the slice. The distance transformed dataset is then linearly interpolated, for instance, between the slices and thresholded at a distance value of zero to obtain interpolated contour or slice points.
The terms pixel and voxel for picture elements and volume elements, respectively, are used interchangeably. Both terms describe elements of planar imaging data which may, particularly in the case of voxels, originate from a slice of a volumetric, three-dimensional object representation.
A disadvantage of the distance field interpolation may be seen in the fact that the resulting interpolated slice also comprises binary image data, i.e., gray value information is lost. Therefore, no sub-pixel accuracy can be achieved using distance field interpolation.
In US patent application 20050091016, Godavarthy et al. describe a method to interpolate or smooth surface points in a triangulated irregular network (TIN).
In EP 1 184 812 A1, Hutter describes a method to smooth unisotropic data sets. In an unisotropic data set slices of an object representation, for instance, are irregularly spaced.
In US patent application number 20030190091A1, Steward describes an iterative method for performing image registration adapted to map features on a first image to corresponding features in a second image.
In U.S. Pat. No. 6,115,048, Cline et al. describe a method for creating or displaying three-dimensional surfaces represented by volume elements tested against a threshold, the surface normal vectors of which may be determined using values of adjacent voxels.
Other commonly used methods for three-dimensional surface reconstruction of medical slice data sets include the “marching squares” and the “marching cubes” algorithms, respectively. A “marching squares” algorithm for generating contour lines from voxels on a contour of a planar slice of a three-dimensional object is described in Maple, C. Geometric Design and Space Planning Using the Marching Squares and Marching Cube Algorithms, International Conference on Geometric Modeling and Graphics (GMAG'03): 90-95, 2003.
Voxels may be considered as being on a contour of an object if they belong to the object and if they are adjacent to at least one voxel that does not belong to the object. A “marching cubes” algorithm that also generates contour lines from voxels of a three-dimensional object but considers voxels in a three-dimensional neighborhood of a contour voxel to determine a surface description of an object by creating a triangulation of the surface of the object is described in Lorensen, W. E. and Cline, H. E. Marching Cubes: A High Resultion 3D Surface Construction Algorithm, Computer Graphics, 21(4): 163—169, 1987.
The smoothness of a surface description resulting from the marching squares or marching cubes algorithm depends on the resolution of the triangulation that has been used. Accurate distance measurement, closest point location, and registration of source points to a target surface are essential methods in surface matching used for medical patient registration.
Surface matching is especially critical if the distance between the slices of a data set is much larger than the voxel or pixel size of the single slices, i.e., the data set may be anisotropic. What is needed is to find a way to interpolate between these slices without creating jagged surfaces, which would prevent a surface matching method from converting to a global minimum.